package book;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class ProjectPlanSolution {

    // 项目任务类
    class ProjectTask {
        int id; // 编号
        int time; // 完成需时
        int indegree; // 入度
        List<ProjectTask> nextTasks = new ArrayList<>(); // 后置任务
        int startTime; // 最早开始时间
        ProjectTask(int i, int t) {
            id = i; time = t;
        }
    }

    // 任务列表，用数组表示
    ProjectTask[] tasks;

    // 维护当前DFS正在处理中的顶点
    Set<Integer> process = new HashSet<>();

    // 返回以起点a出发可以到达的所有邻接点
    List<Integer> next(int a) {
        List<Integer> nextTasks = new ArrayList<>();
        for (ProjectTask task: tasks[a].nextTasks)
            nextTasks.add(task.id);
        return nextTasks;
    }

    // 回溯法寻找有向图中的回退边
    // 如果找到回退边返回true，否则返回false
    boolean dfs(int s) {
        // 判断回退边的根据：搜索到一个顶点已经存在于递归搜索当中
        if (process.contains(s))
            return true;

        // 将当前顶点新加入进dfs搜索顶点
        process.add(s);

        // 搜索下一个顶点
        for (int t: next(s)) {
            // 递归，而且如果在递归搜索中找到回退边，就可以直接返回
            if (dfs(t))
                return true;
        }

        // 记得把搜索完毕的顶点从搜索列表中移除
        process.remove(s);
        return false;
    }

    // 分支限界法进行任务编排
    void bfs() {
        Queue<ProjectTask> queue = new LinkedList<>();
        for (ProjectTask task: tasks) 
            if (task.indegree == 0)
                queue.offer(task);

        int i = 0;
        while (!queue.isEmpty()) {
            ProjectTask st = queue.poll();
            System.out.printf("#%d %d %d\n", ++i, st.id, st.startTime);
            for (ProjectTask t: st.nextTasks) {
                // 更新完成时间及入度，如果入度为0，加入队列
                t.startTime = Math.max(t.startTime, st.startTime + st.time);
                if (--t.indegree == 0)
                    queue.offer(t);
            }
        }
    }

    // 项目任务编排    
    void projectPlan(int n, int[] times, int[][] edges) {
        // 构建图数据结构
        tasks = new ProjectTask[n];
        for (int i = 0; i < n; i++)
            tasks[i] = new ProjectTask(i, times[i]);
        for (int[] ed : edges) {
            int a = ed[0], b = ed[1];
            tasks[a].nextTasks.add(tasks[b]);
            tasks[b].indegree++;
        }

        // 先执行DFS确认任务的合理性
        for (ProjectTask task : tasks) {
            if (task.indegree == 0) {
                if (dfs(task.id)) {
                    System.out.println("任务不合理，存在回退边！");
                    return;
                }
            }
        }

        // 没问题则执行bfs
        bfs();
    }

    public static void main(String[] args) {
        ProjectPlanSolution sln = new ProjectPlanSolution();
        int n = 10;
        int[] times = { 0, 2, 2, 1, 4, 5, 1, 6, 4, 0 };
        int[][] edges = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {2, 5}, {3, 6}, {4, 6}, {5, 7}, {5, 8}, {6, 8}, {7, 9}, {8, 9}};
        sln.projectPlan(n, times, edges);
    }
}
